1. Field of the Invention
This invention relates in general to a system and method for clustering objects in vector space, and in particular to a system and method for clustering objects in a geospatial bitmap.
2. Related Technology
Clustering can be defined as the unsupervised classification of patterns (observations, data items, or feature vectors) into groups (clusters). Clustering algorithms have been developed in support of various disciplines, including biology (e.g., clustering bacterial growth), physics (e.g., clustering high-energy particles), demographics (e.g., clustering populations), medicine (e.g., identifying clusters of tumors), and information technology (e.g., data mining/compression/sorting, image classification/segmentation/retrieval).
Aspects of clustering are described in:    (a) Barnard, J. M. Agglomerative hierarchical clustering package from Barnard Chemical Information, Ltd. Presented at Daylight EUROMUG Meeting, Basel, Switzerland, Dec. 17 (1996);    (b) Can, F. and E. A. Ozkarahan (December 1990) Concepts and effectiveness of the cover-coefficient-based clustering methodology for text databases. ACM TODS 15(4): 483-512;    (c) Cormen, T. H., C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, Cambridge, Mass. (2001);    (d) Day, W. H. E. and H. Edelsbrunner (1984). Efficient algorithms for agglomerative hierarchical clustering methods. Journal of Classification, 1(1), pp. 7-24;    (e) Downs, G. (2001) Clustering in chemistry. Presented at MathFIT workshop, Belfast, April 27;    (f) Downs, G. M. and J. M. Barnard (2003). Clustering methods and their uses in computational chemistry. Reviews in Computational Chemistry, Volume 18, Chapter 1, pp. 5-40. John Wiley and Sons, Inc., New York, N.Y.;    (g) U.S. Pat. No. 6,218,965 B1 to Gendron, M. L., P. B. Wischow, M. E. Trenchard, M. C. Lohrenz, L. M. Riedlinger and M. J. Mehaffey, entitled “Moving Map Composer”, incorporated by reference in its entirety;    (h) Halkidi, M., Y. Batistakis and M. Vazirgiannis (2002). Cluster validity methods: Part II. SIGMOD Record;     (i) Hartigan, J. A. (1975). Clustering Algorithms. John Wiley and Sons, Inc., New York, N.Y.;    (j) Hartigan, J. A. and M. A. Wong (1979). A K-means clustering algorithm. Applied Statistics 28, 100-108;    (j) Ho, T. K. and G. Nagy (2000). OCR with no shape training. In Proceedings of the 15th International Conference on Pattern Recognition, pp. 27-30. Barcelona, Spain, Sep. 3-8;    (k) Hobby, J. and T. K. Ho (1997). Enhancing degraded document images via bitmap clustering and averaging. In Proceedings of the 4th International Conference on Document Analysis and Recognition, pp. 394-400. Ulm, Germany, Aug. 18-20;    (l) Höppner, F., F. Klawonn, R. Kruse and T. Runkler (1999). Fuzzy Cluster Analysis. John Wiley and Sons, Inc., Chicester, England;    (m) Jain, A. K., M. N. Murty, and P J. Flynn (1999). Data clustering: a review. ACM Computing Surveys 31(3). 264-323;    (n) JMPIN V.4.0.4 statistical analysis software package (2003). SAS Institute Inc., Cary, N.C.;    (o) Layne, G., M. Gendron and M. Lohrenz (2004). POS Polyline Smoothing: Reduction of Polyline Vertices. In Proceedings of the Tenth International Conference on Industry, Engineering and Management Systems, Cocoa Beach, Fla. March;    (p) Sibson, R. (1973). SLINK: An Optimally Efficient Algorithm for the Single-Link Cluster Method. Comput. J. 16(1): 30-34;    (q) Spiegel, M. R. (1975). Schaum's outline of theory and problems of probability and statistics. Schaum's outline series. McGraw-Hill, New York, N.Y.;    (r) Voorhees, E. M. (1985a). The effectiveness and efficiency of agglomerative hierarchic clustering in Document Retrieval. Ph.D. Thesis, Cornell University, NY;    (s) Voorhees, E. M. (1985b). The cluster hypothesis revisited. In Proceedings of the 8th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 188-196; and    (t) Yoon, J. P., V. Raghavan, and V. Chakilam (2001). BitCube: a three-dimensional bitmap indexing for XML documents. Journal of Intelligent Information Systems, 17:241-252.